{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #美观的花束"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: beautifulBouquet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #美观的花束"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "力扣嘉年华的花店中从左至右摆放了一排鲜花，记录于整型一维矩阵 `flowers` 中每个数字表示该位置所种鲜花的品种编号。你可以选择一段区间的鲜花做成插花，且不能丢弃。\n",
    "在你选择的插花中，如果每一品种的鲜花数量都不超过 `cnt` 朵，那么我们认为这束插花是 「美观的」。\n",
    "> - 例如：`[5,5,5,6,6]` 中品种为 `5` 的花有 `3` 朵， 品种为 `6` 的花有 `2` 朵，**每一品种** 的数量均不超过 `3`\n",
    "\n",
    "请返回在这一排鲜花中，共有多少种可选择的区间，使得插花是「美观的」。\n",
    "\n",
    "**注意：**\n",
    "- 答案需要以 `1e9 + 7 (1000000007)` 为底取模，如：计算初始结果为：`1000000008`，请返回 `1`\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`flowers = [1,2,3,2], cnt = 1`\n",
    ">\n",
    ">输出：`8`\n",
    ">\n",
    ">解释：相同的鲜花不超过 `1` 朵，共有 `8` 种花束是美观的；\n",
    ">长度为 `1` 的区间 `[1]、[2]、[3]、[2]` 均满足条件，共 `4` 种可选择区间\n",
    ">长度为 `2` 的区间 `[1,2]、[2,3]、[3,2]` 均满足条件，共 `3` 种可选择区间\n",
    ">长度为 `3` 的区间 `[1,2,3]` 满足条件，共 `1` 种可选择区间。\n",
    ">区间 `[2,3,2],[1,2,3,2]` 都包含了 `2` 朵鲜花 `2` ，不满足条件。\n",
    ">返回总数 `4+3+1 = 8`\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`flowers = [5,3,3,3], cnt = 2`\n",
    ">\n",
    ">输出：`8`\n",
    "\n",
    "**提示：**\n",
    "- `1 <= flowers.length <= 10^5`\n",
    "- `1 <= flowers[i] <= 10^5`\n",
    "- `1 <= cnt <= 10^5`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [1GxJYY](https://leetcode.cn/problems/1GxJYY/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [1GxJYY](https://leetcode.cn/problems/1GxJYY/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,2]\\n1', '[5,3,3,3]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        ans = 0\n",
    "        counter = defaultdict(int)\n",
    "        left = 0\n",
    "        for right in range(len(flowers)):\n",
    "            counter[flowers[right]] += 1\n",
    "            while counter[flowers[right]] > cnt:\n",
    "                counter[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        freqs = {}\n",
    "        left = 0\n",
    "        num_intervals = 0\n",
    "        for i in range(len(flowers)):\n",
    "            if flowers[i] not in freqs:\n",
    "                freqs[flowers[i]] = 1\n",
    "            else:\n",
    "                freqs[flowers[i]] += 1\n",
    "            while freqs[flowers[i]] > cnt:\n",
    "                freqs[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            num_intervals = (num_intervals + i - left + 1) % 1000000007\n",
    "        return num_intervals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        d=defaultdict(int)\n",
    "        ans=0\n",
    "        left=0\n",
    "        for right,f in enumerate(flowers):\n",
    "            d[f]+=1\n",
    "            while d[f]>cnt and left<=right:\n",
    "                d[flowers[left]]-=1\n",
    "                left+=1\n",
    "            ans+=right-left+1\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        d = defaultdict(int)\n",
    "        left, right = 0, 0\n",
    "        res = 0\n",
    "        while right < len(flowers):\n",
    "            f = flowers[right]\n",
    "            d[f] += 1\n",
    "            while d[f] > cnt:\n",
    "                d[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            res += (right - left + 1)\n",
    "            right += 1\n",
    "        return res                            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        res=0\n",
    "        count=defaultdict(int)\n",
    "        l = 0\n",
    "        for r in range(len(flowers)):\n",
    "            count[flowers[r]] += 1\n",
    "            while count[flowers[r]]>cnt:\n",
    "                count[flowers[l]]-=1\n",
    "                l+=1\n",
    "            res+=r-l+1\n",
    "            res = res%(1e9+7)\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        d = defaultdict(int)\n",
    "        left, right, res = 0, 0, 0\n",
    "        while right < len(flowers):\n",
    "            f = flowers[right]\n",
    "            d[f] += 1\n",
    "            while d[f] > cnt:\n",
    "                d[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            res += (right - left + 1)\n",
    "            right += 1\n",
    "        return res                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        c = Counter()\n",
    "        for right,x in enumerate(flowers):\n",
    "            c[x] += 1\n",
    "            while c[x] > cnt:\n",
    "                c[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans% (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        cnts = {}\n",
    "        n = len(flowers)\n",
    "        l, r = 0, 0\n",
    "        ans = 0\n",
    "        mod = int(1e9+7)\n",
    "        for r in range(n):\n",
    "            cnts[flowers[r]] = cnts.get(flowers[r], 0) + 1\n",
    "            while cnts[flowers[r]] > cnt:\n",
    "                cnts[flowers[l]] -= 1\n",
    "                l += 1\n",
    "            ans += r - l + 1\n",
    "            ans = ans % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        ans = left = 0\n",
    "        c = Counter()\n",
    "        for right, x in enumerate(flowers):\n",
    "            c[x] += 1\n",
    "            while c[x] > cnt:\n",
    "                c[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        ans = left = 0\n",
    "        c = Counter()\n",
    "        for right, x in enumerate(flowers):\n",
    "            c[x] += 1\n",
    "            while c[x] > cnt:\n",
    "                c[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers, cnt):\n",
    "        MOD = 10**9 + 7\n",
    "        left, right = 0, 0\n",
    "        flower_count = {}\n",
    "        result = 0\n",
    "\n",
    "        while right < len(flowers):\n",
    "            flower = flowers[right]\n",
    "            flower_count[flower] = flower_count.get(flower, 0) + 1\n",
    "\n",
    "            while max(flower_count.values()) > cnt:\n",
    "                left_flower = flowers[left]\n",
    "                flower_count[left_flower] -= 1\n",
    "                if flower_count[left_flower] == 0:\n",
    "                    del flower_count[left_flower]\n",
    "                left += 1\n",
    "\n",
    "            result += right - left + 1\n",
    "            result %= MOD\n",
    "            right += 1\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        ans = left = 0\n",
    "        c = Counter()\n",
    "        for right, x in enumerate(flowers):\n",
    "            c[x] += 1\n",
    "            while c[x] > cnt:\n",
    "                c[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        length = len(flowers)\n",
    "        dp = [0] * (length + 1)\n",
    "        d = defaultdict(deque)\n",
    "        pre_index = -1\n",
    "\n",
    "        for i in range(length):\n",
    "            if len(d[flowers[i]]) == cnt:\n",
    "                tmp = d[flowers[i]].popleft()\n",
    "                if tmp > pre_index:\n",
    "                    pre_index = tmp\n",
    "            dp[i+1] = i - pre_index + dp[i]\n",
    "            d[flowers[i]].append(i)\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        ans = left = 0\n",
    "        c = defaultdict(int)\n",
    "        for right, x in enumerate(flowers):\n",
    "            c[x] += 1\n",
    "            while c[x] > cnt:\n",
    "                c[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        r=0\n",
    "        l=0\n",
    "        n=len(flowers)\n",
    "        ans=0\n",
    "        q=Counter()\n",
    "        def g(q):\n",
    "           for x in q.items():\n",
    "               if x[1]>cnt:\n",
    "                   return True\n",
    "           return False          \n",
    "        while r<n:\n",
    "           q[flowers[r]]+=1\n",
    "           while g(q):\n",
    "               q[flowers[l]]-=1\n",
    "               \n",
    "               l+=1\n",
    "           ans+=r-l+1\n",
    "           r+=1   \n",
    "        return ans%(10**9+7)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        mod=10**9+7\n",
    "        d=defaultdict(int)\n",
    "        l,r=0,0\n",
    "        res=0\n",
    "        while r<len(flowers):\n",
    "            x=flowers[r]\n",
    "            d[x]+=1\n",
    "            r+=1\n",
    "            while d[x]>cnt:\n",
    "                d[flowers[l]]-=1\n",
    "                l+=1\n",
    "            res+=r-l\n",
    "            res%=mod\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        res=0\n",
    "        count=defaultdict(int)\n",
    "        l = 0\n",
    "        for r in range(len(flowers)):\n",
    "            count[flowers[r]] += 1\n",
    "            while count[flowers[r]]>cnt:\n",
    "                count[flowers[l]]-=1\n",
    "                l+=1\n",
    "            res+=r-l+1\n",
    "            res = res%(1e9+7)\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: list[int], cnt: int) -> int:\n",
    "        left, right = 0,0\n",
    "        dict = Counter()\n",
    "        n = len(flowers)\n",
    "        result = 0\n",
    "        while right<n:\n",
    "            dict[flowers[right]]+=1\n",
    "            while dict[flowers[right]]>cnt:\n",
    "                dict[flowers[left]] -= 1\n",
    "                left+=1\n",
    "            result += right-left+1\n",
    "            right+=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        c = Counter()\n",
    "        for right,x in enumerate(flowers):\n",
    "            c[x] += 1\n",
    "            while c[x] > cnt:\n",
    "                c[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, f: List[int], a: int) -> int:\n",
    "        m = 10**9 + 7\n",
    "        n = len(f)\n",
    "        c = Counter([])\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            c[f[j]] += 1 \n",
    "            while c[f[j]]>a:\n",
    "                c[f[left]] -= 1\n",
    "                left += 1 \n",
    "            ans += j - left + 1 \n",
    "        return ans%m\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        ans = 0\n",
    "        c = Counter()\n",
    "        left = 0\n",
    "        for right, x in enumerate(flowers):\n",
    "            c[x] += 1\n",
    "            while c[x] > cnt:\n",
    "                c[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        ans = left = 0\n",
    "        c = Counter()\n",
    "        for right, x in enumerate(flowers):\n",
    "            c[x] += 1\n",
    "            while c[x] > cnt:\n",
    "                c[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: list[int], cnt: int) -> int:\n",
    "        left, right = 0,0\n",
    "        dict = defaultdict(int)\n",
    "        n = len(flowers)\n",
    "        result = 0\n",
    "        while right<n:\n",
    "            dict[flowers[right]]+=1\n",
    "            while dict[flowers[right]]>cnt:\n",
    "                dict[flowers[left]] -= 1\n",
    "                left+=1\n",
    "            result += right-left+1\n",
    "            right+=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        ans = left = 0\n",
    "        c = Counter()\n",
    "        for right, x in enumerate(flowers):\n",
    "            c[x] += 1\n",
    "            while c[x] > cnt:\n",
    "                c[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        ans=left=0\n",
    "        c=Counter()\n",
    "        for right,x in enumerate(flowers):\n",
    "            c[x]+=1\n",
    "            while c[x]>cnt:\n",
    "                c[flowers[left]]-=1\n",
    "                left+=1\n",
    "            ans+=right-left+1\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        ans = left = 0\n",
    "        c = Counter()\n",
    "        for right, x in enumerate(flowers):\n",
    "            c[x] += 1\n",
    "            while c[x] > cnt:\n",
    "                c[flowers[left]] -= 1\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        ans=Counter()\n",
    "        l=r=0\n",
    "        res=0\n",
    "        while r<len(flowers):\n",
    "            ans[flowers[r]]+=1\n",
    "            while ans[flowers[r]]>cnt:\n",
    "                ans[flowers[l]]-=1\n",
    "                l+=1\n",
    "            res+=r-l+1\n",
    "            r+=1\n",
    "        return res%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        mod = 1000000007\n",
    "        counter = collections.defaultdict(int)\n",
    "        left, right = 0, 0\n",
    "        ans = 0\n",
    "\n",
    "        while right < len(flowers):\n",
    "            # Increase the count of flower at 'right' index\n",
    "            counter[flowers[right]] += 1\n",
    "            \n",
    "            # If any flower's count exceeds 'cnt', move 'left' pointer\n",
    "            while any(val > cnt for val in counter.values()):\n",
    "                counter[flowers[left]] -= 1\n",
    "                if counter[flowers[left]] == 0:\n",
    "                    del counter[flowers[left]]\n",
    "                left += 1\n",
    "\n",
    "            # Answer is increased by the number of valid intervals ending at 'right'\n",
    "            ans += (right - left + 1)\n",
    "            right += 1\n",
    "\n",
    "        return ans % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "\n",
    "        # 1,2,3,2,3,1,3,2,1,1,2,2,3,3,1,2,1    2\n",
    "        # 1,2,3,2,3,1\n",
    "        # 0, 1, 2, 3, 4, 5, 3, 4\n",
    "\n",
    "\n",
    "        # one tranverse to get the boudary of one side like left to right\n",
    "\n",
    "        n = len(flowers)\n",
    "        left_boundary = [0] * n\n",
    "\n",
    "        d = defaultdict(Deque)\n",
    "        pre = 0\n",
    "        for i, f in enumerate(flowers):\n",
    "\n",
    "            d[f].append(i)\n",
    "            if len(d[f]) > cnt:\n",
    "                pre = max(pre, d[f].popleft() + 1)\n",
    "            \n",
    "            left_boundary[i] = pre\n",
    "        \n",
    "        #print(left_boundary)\n",
    "\n",
    "        # right_boundary = [0] * n\n",
    "        # d = defaultdict(Deque)\n",
    "        # pre = n\n",
    "\n",
    "        # for i in range(n-1, -1, -1):\n",
    "        #     f = flowers[i]\n",
    "\n",
    "        #     d[f].append(i)\n",
    "        #     if len(d[f]) > cnt:\n",
    "        #         pre = min(pre, d[f].popleft() - 1)\n",
    "            \n",
    "        #     right_boundary[i] = pre\n",
    "        \n",
    "        #print(right_boundary)\n",
    "\n",
    "        P = 10**9 + 7\n",
    "        ret = 0\n",
    "        for i, b in enumerate(left_boundary):\n",
    "\n",
    "            ret += (i - b + 1)\n",
    "        \n",
    "        return ret % P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        length = len(flowers)\n",
    "        dp = [0] * (length + 1)\n",
    "        d = defaultdict(list)\n",
    "        pre_index = -1\n",
    "\n",
    "        for i in range(length):\n",
    "            if len(d[flowers[i]]) == cnt:\n",
    "                pre_index = max(d[flowers[i]].pop(0), pre_index)\n",
    "            dp[i+1] = i - pre_index + dp[i]\n",
    "            d[flowers[i]].append(i)\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:\n",
    "        length = len(flowers)\n",
    "        dp = [0] * (length + 1)\n",
    "        d = defaultdict(list)\n",
    "        pre_index = -1\n",
    "\n",
    "        for i in range(length):\n",
    "            if len(d[flowers[i]]) == cnt:\n",
    "                tmp = d[flowers[i]].pop(0)\n",
    "                if tmp > pre_index:\n",
    "                    pre_index = tmp\n",
    "            dp[i+1] = i - pre_index + dp[i]\n",
    "            d[flowers[i]].append(i)\n",
    "\n",
    "        return dp[-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
